public class Solution563 {

    int ans;

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(int val) {
            this.val = val;
        }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public int findTilt(TreeNode root) {
        ans=0;
        deal(root);
        search(root);
        return ans;
    }

    public void search(TreeNode root){
        if (root==null){
            return;
        }
        search(root.left);
        search(root.right);
        int a=root.left==null?0:root.left.val;
        int b=root.right==null?0:root.right.val;
        ans+=Math.abs(a-b);
    }

    public void deal(TreeNode root){
        if (root==null){
            return;
        }
        if (root.left!=null){
            deal(root.left);
            root.val+=root.left.val;
        }
        if (root.right!=null){
            deal(root.right);
            root.val+=root.right.val;
        }
    }

    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(3,new TreeNode(2,null,null),new TreeNode(1,null,null));
        System.out.println(new Solution563().findTilt(treeNode));
    }
}
